#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    void Combinations(string digits, string& s, vector<string>& vv, vector<string>& res, int n)
    {
        if (n == digits.size())
        {
            res.push_back(s);
            return;
        }
        int index = digits[n] - '0';
        for (int i = 0; i < vv[index].size(); ++i)
        {
            s.push_back(vv[index][i]);
            Combinations(digits, s, vv, res, n + 1);
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits == "")
        {
            return vector<string>();
        }
        vector<string> vv = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
        vector<string> res;
        string s;
        Combinations(digits, s, vv, res, 0);
        return res;
    }
};
int main()
{
    string l = "58";
    vector<string> res = Solution().letterCombinations(l);
    for (auto& ch : res)
    {
        cout << ch << ' ';
    }
    return 0;
}